package com.sise.Tree;

/**
 *      114. 二叉树展开为链表
 *
 *      给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *      展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 *      展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *
 */
public class _114_flatten {
    public void flatten(TreeNode root) {
        // 当节点不为空的时候，就可以一直往下遍历
        while (root != null){
            if (root.left == null){             // 这里做的是优化操作，如果左子树为 null，直接考虑下一个节点
                root = root.right;
            }else {
                TreeNode pre = root.left;       // 找到左子树 最右边的节点（最大的节点）。这里不只是简单的找到 左子树的第一个节点
                while (pre.right != null){
                    pre = pre.right;
                }


                pre.right = root.right;     // 将右子树接到 pre 左子树的最右边节点 后面
                root.right = root.left;     // 将左子树替换右子树，这不能用 root.right = pre，因为 pre 是左子树最右边的一个节点，而我们需要的是整颗左子树
                root.left = null;           // 将左子树置空
                root = root.right;          // 考虑下一个节点
            }
        }
    }
}
